package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jonny Long
 * @date 2021/3/19 9:00
 */
public class Solution07 {
    private Map<Integer,Integer> indexMap;

    /**
     * 递归操作：找到每一步的根节点，作为父亲的左孩子或者右孩子
     * @param preOrder 先序数组
     * @param inOrder 中序数组
     * @param preLeft 先序左边界
     * @param preRight 先序右边界
     * @param inLeft 中序左边界
     * @param inRight 中序右边界
     * @return 某次递归的根节点
     */
    private TreeNode myBuildTree(int[] preOrder, int[] inOrder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        int preRoot = preLeft;
        int inRoot = indexMap.get(preOrder[preRoot]);
        TreeNode root = new TreeNode(preOrder[preRoot]);
        // 左子树节点个数=中序根位置-最左节点位置
        int sizeLeftSubtree = inRoot - inLeft;
        root.left = myBuildTree(preOrder, inOrder, preLeft + 1, preLeft + sizeLeftSubtree, inLeft, inRoot - 1);
        root.right = myBuildTree(preOrder, inOrder, preLeft + sizeLeftSubtree + 1, preRight, inRoot + 1, inRight);
        return root;
    }

    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        int n = preOrder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inOrder[i], i);
        }
        return myBuildTree(preOrder, inOrder, 0, n - 1, 0, n - 1);
    }
}
